In computer systems it is common that a given resource (such as a system bus, a memory bank, etc.) is shared between several competing requesting devices or processes (“requesters”) that would like to make use of the resource. Access to that resource therefore has to be arbitrated, in order to determine which requester can access the resource when there are concurrent and conflicting requests to the resource. It is desirable to be able to specify different quality-of-service (QOS) guarantees for different requestors in order for the system to operate properly. Examples of QOS guarantees include data bandwidth and latency. For example, it may be desirable to allow a processor to have very high-priority and therefore low-latency access to a memory system. Another example is that one might want a video system to have a certain reserved bandwidth on a system bus so that the video screen can be updated as required at a fixed frame rate.
Existing arbitration schemes that aim to provide QOS guarantees include fixed-priority arbitration and time division multiplexing. In fixed-priority arbitration each requestor is assigned a fixed priority and requesters are serviced in priority order. In time division multiplexing, each requestor is pre-allocated a certain set of fixed access periods during which it can access the resource. While these arbitration schemes have their value in certain systems, they fall short of providing QOS guarantees when there is a mix of requesters with different QOS requirements and perhaps unpredictable request arrival times. For example, it is not possible to give any kind of bandwidth guarantee to multiple different requestors if fixed-priority arbitration is used unless the exact request pattern of each initiator is known a priori. Time division multiplexing is inefficient when the arrival times of requests are not deterministic, or when the requests require differing amounts of service time from the resource depend on the type of request or the recent history of other requests.
What is desired is a resource scheduling scheme that can provide different QOS guarantees to different requesters and further can efficiently handle non-deterministic arrival and service times.